package com.squirrel.michale;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/3/25 6:51 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode0864 {


    public int shortestPathAllKeys(String[] grid) {
        int[][] directions = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
        int m = grid.length;
        int n = grid[0].length();
        Deque<int[]> deque = new ArrayDeque<>();
        int keyCount = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char ch = grid[i].charAt(j);
                if (ch == '@') {
                    deque.offer(new int[]{i,j,0,0});
                } else if (ch >= 'a' && ch <= 'f') {
                    keyCount++;
                }
            }
        }
        int keyStatusCount = 1 << keyCount;
        int keyStatusFull = keyStatusCount - 1;
        int[][][] visited = new int[m][n][keyStatusCount];
        while (!deque.isEmpty()) {
            int[] cur = deque.poll();
            int x = cur[0];
            int y = cur[1];
            int steps = cur[2];
            int keyStatus = cur[3];
            if (keyStatus == keyStatusFull) {
                return steps;
            }
            for (int[] direction:directions) {
                int newX = direction[0] + x;
                int newY = direction[1] + y;
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX].charAt(newY)!='#') {
                    char curChar = grid[newX].charAt(newY);
                    if (curChar >= 'A' && curChar <= 'F') {
                        if ((keyStatus >> (curChar - 'A') & 1) == 1 && visited[newX][newY][keyStatus] == 0) {
                            visited[newX][newY][keyStatus] = 1;
                            deque.offer(new int[]{newX, newY, steps + 1, keyStatus});
                        }
                    } else if (curChar >= 'a' && curChar <= 'f') {
                        int newKey = keyStatus | (1 << curChar - 'a');
                        if (visited[newX][newY][newKey] == 0) {
                            visited[newX][newY][newKey] = 1;
                            deque.offer(new int[]{newX, newY, steps + 1, newKey});
                        }
                    }else{
                        if (visited[newX][newY][keyStatus] == 0) {
                            visited[newX][newY][keyStatus] = 1;
                            deque.offer(new int[]{newX, newY, steps + 1, keyStatus});
                        }
                    }
                }
            }
        }
        return -1;
    }




    public int shortestPathAllKeys2(String[] grid) {
        int[][] directions = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
        int m = grid.length;
        int n = grid[0].length();
        Deque<int[]> deque = new LinkedList<>();
        int keyCount = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char ch = grid[i].charAt(j);
                if (ch == '@') {
                    deque.offer(new int[]{i,j,0,0});
                } else if (ch >= 'a' && ch <= 'f') {
                    keyCount++;
                }
            }
        }
        int keyStatusFull = (1 << keyCount) - 1;
        int[][][] visited = new int[m][n][1 << keyCount];
        while (!deque.isEmpty()) {
            int[] cur = deque.poll();
            int x = cur[0];
            int y = cur[1];
            int steps = cur[2];
            int keyStatus = cur[3];
            if (keyStatus == keyStatusFull) {
                return steps;
            }
            for (int[] direction:directions) {
                int newX = direction[0] + x;
                int newY = direction[1] + y;
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX].charAt(newY)!='#') {
                    char curChar = grid[newX].charAt(newY);
                    if (curChar >= 'A' && curChar <= 'F') {
                        if ((keyStatus >> (curChar - 'A') & 1) == 1 && visited[newX][newY][keyStatus] == 0) {
                            visited[newX][newY][keyStatus] = 1;
                            deque.offer(new int[]{newX, newY, steps + 1, keyStatus});
                        }
                    } else if (curChar >= 'a' && curChar <= 'f') {
                        int newKey = keyStatus | (1 << curChar - 'a');
                        if (visited[newX][newY][newKey] == 0) {
                            visited[newX][newY][newKey] = 1;
                            deque.offer(new int[]{newX, newY, steps + 1, newKey});
                        }
                    }else{
                        if (visited[newX][newY][keyStatus] == 0) {
                            visited[newX][newY][keyStatus] = 1;
                            deque.offer(new int[]{newX, newY, steps + 1, keyStatus});
                        }
                    }
                }
            }
        }
        return -1;
    }

}
